public class TestDemo {

    public static void main(String[] args) {
        //链表的回文结构
        if (head == null) {
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //slow走到了中间位置
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //反转完成
        while (head != slow) {
            if (head.val != slow.val) {
                return fasle;
            }
            if (head.next = slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}


    public static void main1(String[] args) {
        //输入两个链表，找出他们的公共结点
        if (headA == null || headB == null){
            return null;
        }
        ListNode pl = headA;
        ListNode ps = headB;
        int lenA = 0;
        int lenB = 0;
        while (pl != null) {
            lenA++;
            pl = pl.next;
        }
        pl = headA;
        while (ps != null) {
            lenB++;
            ps = ps.next;
        }
        ps = headB;
        int len = lenA - lenB;
        if (len < 0) {
            pl = lenB;
            ps = lenA;
            len = lenB - lenA;
        }
        //1、pl永远指向最长的链表，ps永远指向了最短的链表
        //2、求到了差值len步

        //pl走差值len步
        while (len != 0) {
            pl = pl.next;
            len--;
        }
        //同时走，直到相遇
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        return pl;
    }


    public static void main2(String[] args) {
        //给定一个链表，判断链表中是否有环
        if (head = null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        /*while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                return true;
            }
        }
        return false;*/

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                break;
            }
        }
        if (fast == null && fast.next == null){
            return false;
        }
        return true;
    }


    public static void main(String[] args) {
        //给定一个链表，返回链表开始入环的第一个结点，如果链表无环，则返回null
        if (head = null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == null && fast.next == null) {
            return null;
        }
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
}
